Learning marginals suffices!

Abstract: Beyond computer science, quantum complexity theory can potentially revolutionize multiple branches of physics, ranging from quantum many-body systems to quantum field theory. I will present our work that centers on the intriguing relationship between the sample complexity of learning a quantum state and its circuit complexity. Our tool is a kind of quantum overlapping tomography, which only relies on random Pauli measurements. Our proof overcomes difficulties characterizing short-range entanglement by bridging quantum circuit complexity and ground states of gapped local Hamiltonians. Our result, for example, settles the quantum circuit complexity of the multi-qubit GHZ state exactly.This is a joint work with Nengkun Yu, arXiv:arXiv:2303.08938

quantum computing and informationMathematicsPhysics

Audience: researchers in the topic

Mathematical Picture Language Seminar